#include<stdio.h>
#include<malloc.h>
#include<string.h>

#define MAX_FILE_NAME 10



typedef struct fileDescriptor{
	char filename[MAX_FILE_NAME];
}f_desc;



typedef struct linkedlist{
	void *key;
	void *data;
	struct linkedlist *next;
}l_node;


typedef struct linkedlistforSearch{
	char data[MAX_FILE_NAME];
	struct linkedlistforSearch *next;
}l_nodeSearch;


typedef struct hash_table
{
l_node *htable[62];
}hash;





l_node *createNode()
{
	l_node *newNode = (l_node *)malloc(sizeof(l_node));
	return newNode;
}


l_node *insert(l_node *start, char f_name[])
{
	l_node *newNode, *currNode, *prevNode;

	newNode=createNode();

	//assigning filename address to key
	newNode->key=(char *) malloc(sizeof(char )*10);
	strcpy((char *)newNode->key,f_name);


	//creating a node of the type f_desc, to which data part of the LL will point
	newNode->data = (f_desc *)malloc(sizeof(f_desc));
	strcpy(((f_desc *)(newNode->data))->filename, f_name);

	//((f_desc *)(newNode->data))->filename=(char *) malloc(sizeof(char)*10);

	//point to the next node of LL
	newNode->next=NULL;
	
	if(start==NULL)
	{
	start=newNode;
	
	}
	else
	{
	//insert in sorted order
	currNode=start;
	prevNode=NULL; //This has to be NULL initially (not compulsory)
	while((currNode!=NULL) && (strcmp(f_name, (char *)currNode->key)>0))
	{
	prevNode=currNode;
	currNode=currNode->next;
	}
	if(currNode==NULL)
	{
	prevNode->next=newNode;
	}
	else
	{
	if(currNode==start) //insert at the beginning, hence need to change the start of LL
	{
	newNode->next=currNode;
	start=newNode;
	}
	
	else // insert somewhere in the middle but not in the beginning
	{
	newNode->next=currNode;
	prevNode->next=newNode;
	}
	}
	}
	return start;
}




int hash_value(char var){

	if(var >= '0' && var <= '9')
	{
		return var - '0';
	}
	
	else if(var >= 'A' && var <= 'Z')
	{
		return var - 'A' + 10;
	}
	
	else if(var >= 'a' && var <= 'z')
	{
		return var - 'a' + 10 + 26;
	}
}



hash *hash_insert(hash *ht_start, char filename[])
{
	char var;
	int index;
	
	var = filename[0];
	index = hash_value(var);
	
	ht_start->htable[index] = insert(ht_start->htable[index], filename);
	
	return ht_start;
}




 void hash_initialize(hash *ht)
{
	int i,flag=1;
	if(ht == NULL) flag=0;
	//return;
	for(i = 0;(i<62 && flag);i++)
	{
	ht->htable[i] = NULL;
	}
}



void display(l_node *start)
{
	l_node *temp = start;
	while(temp!=NULL)
	{
		printf("  %s", (char *)temp->key);
		temp=temp->next;
	}
	printf("\n");
}



void display_hashTable(hash *ht_start)
{
	int i;
	for(i=0;i<62;i++)
	{
		display(ht_start->htable[i]);
		printf("\n");
	}
}



//Search:





l_nodeSearch *insertinSearchlinkedlist(l_nodeSearch *startoflinkedlistSearch, char key[])
{
	l_nodeSearch *temp, *newNode;
	temp=startoflinkedlistSearch;

	newNode = (l_nodeSearch *)malloc(sizeof(l_nodeSearch));
	strcpy(newNode->data,key);
	newNode->next=NULL;

	if(temp==NULL)
	{
		startoflinkedlistSearch = newNode;
	}
	else
	{
		while(temp->next != NULL)
		{
			temp=temp->next;
		}
		temp->next=newNode;
	}
	return startoflinkedlistSearch;	
}




l_nodeSearch *SearchByStringKey(l_node *start, char key[])
{
	l_nodeSearch *startoflinkedlistSearch=NULL, *newNode, *t;

	//startoflinkedlistSearch = (l_nodeSearch *)malloc(sizeof(l_nodeSearch));
	
	char nodeKey[MAX_FILE_NAME];
	l_node *temp;
	temp=start;	

	while(temp!=NULL)
	{
		if( strcmp((char *)temp->key, key)==0)
		{
			startoflinkedlistSearch=insertinSearchlinkedlist(startoflinkedlistSearch, key);			
		}	
		temp=temp->next;
		if(temp==NULL)
		{
			return startoflinkedlistSearch;
		}
	}	
	printf("\nSearch completed! No records found\n");
	return NULL;
}





//not in vfslinkedlist.c
l_nodeSearch *search_hashTable(hash *ht_start, char filename[])
{

	char var;
	int index;
	l_nodeSearch *searchStart;
	
	var = filename[0];
	index = hash_value(var);
	
	searchStart = SearchByStringKey(ht_start->htable[index], filename);
	
	return searchStart;
}



void displaySearchResults(l_nodeSearch *startofSearchlinkedlist)
{
	
	l_nodeSearch *temp;
	temp=startofSearchlinkedlist;

	while(temp!=NULL)
	{
		printf("%s  ",temp->data);
		temp = temp->next;
	}
}





//Delete...


l_node *deleteFromLinkedlist(l_node *start, char filename[])
{
	l_node *currNode, *prevNode;
	prevNode=NULL;
	currNode=start;
	if(start!=NULL)
	{
	
		if(strcmp((char *)currNode->key, filename)==0)
		{
			start=currNode->next;
			free(currNode);
			printf("\nDeletion Successful.");
		}
		else
		{
			while(currNode!=NULL && strcmp((char *)currNode->key, filename)!=0)
			{
				prevNode=currNode;
				currNode=currNode->next;
			}
			if(currNode==NULL)
			{
				printf("\nThe filename you entered does not exist.");
			}
			else
			{
				prevNode->next=currNode->next;
				free(currNode);
				printf("\nDeletion Successful.");
			}
		}
	}
	else
	{
		printf("\n\nDeletion Unsuccessful! Hash Table is emty.");
	}
	return start;
}


//we can also implement the return via (l_node *)
void deleteFromHashTable(hash *ht_start, char filename[])
{
	l_node *deletedStart;
	char var;
	int index;
	l_nodeSearch *searchStart;
	
	var = filename[0];
	index = hash_value(var);
	deletedStart = deleteFromLinkedlist(ht_start->htable[index], filename);
	ht_start->htable[index] = deletedStart;
	
	//return deletedStart;
}

void main()
{
	hash *ht_start;	
	int choice;
	char filename[10];
	l_nodeSearch *searchStart;
		
	ht_start=(hash *)malloc(sizeof(hash));
		
	hash_initialize(ht_start);
	
	do
	{
		printf("\nEnter filename: ");
		fflush(stdin);
		scanf("%s", filename);
		ht_start = hash_insert(ht_start, filename);
		printf("Hit -1 to exit... else any number to continue...");
		scanf("%d", &choice);
		
	}while(choice!=-1);		
	
	printf("\nInsertion Successful...");
	printf("\n\n*****DISPLAY FROM HASH TABLE*****\n");
	display_hashTable(ht_start);
	
	printf("\n*****SEARCH IN HASH TABLE*****");
	do
	{
		printf("\n\nEnter File name to search:  ");
		fflush(stdin);
		scanf("%s", filename);
		
		searchStart = search_hashTable(ht_start, filename);
		
		displaySearchResults(searchStart);	
		
		printf("\nHit -1 to exit, else any number to continue searching...");
		scanf("%d", &choice);
		
	}while(choice!=-1);
	
	
	printf("\n\n\n*****DELETE THROUGH HASH TABLE*****");
	do
	{
		printf("\n\nEnter File name to delete:  ");
		fflush(stdin);
		scanf("%s", filename);
		
		deleteFromHashTable(ht_start, filename);
		display_hashTable(ht_start);		//check
		
		printf("\nHit -1 to exit, else any number to continue searching...");
		scanf("%d", &choice);
		
	}while(choice!=-1);
			
	
	
	
	printf("\n\n*****TESTING*****");
	
	printf("\n\nInsertion:  \n");
	do
	{
		printf("\nEnter filename: ");
		fflush(stdin);
		scanf("%s", filename);
		ht_start = hash_insert(ht_start, filename);
		printf("Hit -1 to exit... else any number to continue...");
		scanf("%d", &choice);
		
	}while(choice!=-1);	
	
	printf("\n\nDisplay:   \n");
	display_hashTable(ht_start);
}
